package com.arron.algorithm.leetcodetop100.动态规划;


/**
 * Leetcode 70. 爬楼梯
 */
public class ClimbStairs {

    public static void main(String[] args) {
        long  t =   System.currentTimeMillis();
        System.out.println(climbStairs2(44));
        System.out.println("耗时 ： "+(System.currentTimeMillis()-t) +"ms");
    }

    /**
     * 没有优化的递归，会有重复的递归调用
     *  时间复杂度 ：O(2n) 2n为2的n次方
     *  空间复杂度为 O(n)
     * @param n
     * @return
     */
    public static int climbStairs(int n) {
        if (n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1) + climbStairs(n-2);
    }


    /**
     * 记忆化递归，去掉重复的递归
     * 时间复杂度 ：O(n)
     * 空间复杂度 ：O(n)
     * @param n
     * @return
     */
    public static int climbStairs2(int n) {
      int a[] = new int[n+1];
       return climbStairs21(n,a);
    }

    public static int climbStairs21(int n,int[] a) {
        if (a[n] >0){
            return a[n];
        }
        if(n==1){
            a[n] = 1;
        }else if (n==2){
            a[n] =2;
        }else {
            a[n] = climbStairs21(n-1,a) + climbStairs21(n-2,a);
        }
        return a[n];
    }


    /**
     * 使用动态规划的思想
     * @param n
     * @return
     */
    public static int climbStairs3(int n) {

        if (n==1) return 1;
        if (n==2) return 2;

        int dp[] = new int[n+1];

        dp[1] = 1;
        dp[2] =2;

        for (int i = 3; i <=n; i++) {

            dp[i] = dp[i-1] +dp[i-2];

        }
        return dp[n];
    }





}
